import collections
from typing import List

# 拓扑排序 O(N+M)

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)  # 结点数量
        m = len(edges)  # 边的数量

        # 统计每个结点的入射边数量和出射边列表
        in_count = [0] * n
        out_count = [[] for _ in range(n)]
        for a, b in edges:
            in_count[b] += 1
            out_count[a].append(b)
        # print("入射边数量:", in_count)
        # print("出射边列表:", out_count)

        # 寻找所有根结点
        root_list = collections.deque()
        for i in range(n):
            if in_count[i] == 0:
                root_list.append(i)

        # 定义状态矩阵：dp[i][j]=到达结点i的路径中，颜色j的最大值
        dp = [[0] * 26 for _ in range(n)]

        ans = 0

        # 执行基于拓扑排序的动态规划
        visited_num = 0
        while root_list:
            i = root_list.popleft()

            # 更新当前结点的状态：增加自身的颜色
            color = colors[i]
            dp[i][ord(color) - 97] += 1
            ans = max(ans, max(dp[i]))

            # print("结点:", i, dp[i], "->", max(dp[i]))

            # 更新当前结点所有子结点的状态：
            for j in out_count[i]:
                dp[j] = [max(dp[i][c], dp[j][c]) for c in range(26)]
                in_count[j] -= 1
                if in_count[j] == 0:
                    root_list.append(j)

            visited_num += 1

        # 存在环导致拓扑排序无法遍历某些点
        if visited_num < n:
            return -1

        return ans


if __name__ == "__main__":
    print(Solution().largestPathValue(colors="abaca", edges=[[0, 1], [0, 2], [2, 3], [3, 4]]))  # 3
    print(Solution().largestPathValue(colors="a", edges=[[0, 0]]))  # -1

    # 自制用例
    print(Solution().largestPathValue(colors="abc", edges=[[0, 1], [1, 0]]))  # -1
